package test;

import java.util.HashMap;
import java.util.Map;

class LRUCache {

    //定义双向链表
    class DlinkNode {
        int key;
        int value;
        int expireTime;
        DlinkNode prev;
        DlinkNode next;
        public DlinkNode() {}
        public DlinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public DlinkNode(int key, int value, int expireTime) {
            this.key = key;
            this.value = value;
            this.expireTime = expireTime;//这里的超时时间是当前时间+有效时间，put/get的时候检查是否过期，get过期了返回-1;put过期了重新新建
        }
    }
    
    private Map<Integer, DlinkNode> map=new HashMap<Integer, DlinkNode>();
    private int size;
    private int capacity;
    private DlinkNode head,tail;//类里定义属性，和方法，方法里才能定义操作

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size=0;
        head=new DlinkNode();
        tail=new DlinkNode();
        head.next=tail;
        tail.prev=head;
    }
    
    
    public int get(int key) {
        //如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 ,更新其操作时间
        if (map.containsKey(key)) {
            DlinkNode node=map.get(key);
            moveToHead(node);
            return node.value;
        }else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        //判断是否存在，存在+1，并且放到头部
        if (map.containsKey(key)) {
            DlinkNode node=map.get(key);
            node.value = value;
            moveToHead(node);
        }else {//不存在，先新建，再判断是否需要逐出
            DlinkNode node=new DlinkNode(key,value);
            addToHead(node);
            map.put(key,node);
            size++;
            if (size>capacity) {
                DlinkNode dlinkNode = removeLastNode();
                map.remove(dlinkNode.key);
                size--;
            }
        }
    }

    //
    private void moveToHead(DlinkNode node) {
        removeNode(node);
        addToHead(node);
    }

    //移除某个节点
    private void removeNode(DlinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    //将某个节点添加到头部
    private void addToHead(DlinkNode node) {
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }

    //移除尾部节点
    private DlinkNode removeLastNode() {
        DlinkNode node=tail.prev;
        removeNode(node);
        return node;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);
        cache.put(3, 3);
        cache.get(2);
    }
}
